package tree.binarysearchtree;

import tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname : LowestCommonAncestorOfABinaryTree
 * @Description :
 * <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/">236. 二叉树的最近公共祖先</a>
 * @Author : chentianyu
 * @Date 2023/1/26 16:16
 */


public class LowestCommonAncestorOfABinaryTree {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pPath = new ArrayList<>();
        List<TreeNode> qPath = new ArrayList<>();
        TreeNode ans = null;

        getPath(root, pPath, p.val);
        getPath(root, qPath, q.val);

        // 遍历两个路径找到最近公共祖先节点
        for (int i = 0; i < Math.min(pPath.size(), qPath.size()) && pPath.get(i) == qPath.get(i); i++) {
            ans = pPath.get(i);
        }
        return ans;
    }

    /**
     * 获取从根节点到目标节点的路径
     *
     * @param root
     * @param path
     * @param target
     * @return
     */
    private boolean getPath(TreeNode root, List<TreeNode> path, int target) {
        if (root == null) return false;
        path.add(root);
        if (root.val == target) return true;
        boolean res = (getPath(root.left, path, target) || getPath(root.right, path, target));
        if (!res) path.remove(root);
        return res;
    }
}
